//
// Description: 39. 组合总和
// Created by Loading on 2022/4/3.
//

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
    int n = candidates.size();
    vector<vector<int>> res;
    vector<int> tmp;

    // 需要先排序
    sort(candidates.begin(), candidates.end());
    function<void(int, int)> backtrack = [&](int sum, int index) {
        if (sum == target) {
            res.emplace_back(tmp);
        } else {
            for (int i = index; i < n; ++i) {
                // 和已超出target，剪枝
                if (sum + candidates[i] > target) {
                    break;
                }
                tmp.emplace_back(candidates[i]);
                backtrack(sum + candidates[i], i);
                tmp.pop_back();
            }
        }
    };

    backtrack(0, 0);

    return res;
}

int main() {
    vector<int> candidates{2, 3, 6, 7};
    int target = 7;
    auto res = combinationSum(candidates, target);
    for (auto v : res) {
        for (auto x : v) {
            cout << x << ' ';
        }
        cout << endl;
    }

    return 0;
}